1. Field of the Invention
The present invention relates generally to data processing systems, and in particularly to a method and system for scheduling threads on a data processing system. Still more particularly, the present invention relates to a method and system for scheduling threads on a data processing system wherein system resources are allocated based on a priority determination of a thread.
2. Description of the Related Art
The basic structure of a conventional computer system includes a system bus or a direct channel that connects one or more processors to input/output (I/O) devices (such as a display monitor, keyboard and mouse), a permanent memory device for storing the operating system and user programs (such as a magnetic hard disk), and a temporary memory device that is utilized by the processors to carry out program instructions (such as random access memory or xe2x80x9cRAMxe2x80x9d).
When a user program runs on a computer, the computer""s operating system (OS) first loads the program files into system memory. The program files include data objects and instructions for handling the data and other parameters which may be input during program execution.
The operating system creates a process to run a user program. A process is a set of resources, including (but not limited to) values in RAM, process limits, permissions, registers, and at least one execution stream. Such an execution stream is commonly termed a xe2x80x9cthread.xe2x80x9d The utilization of threads in operating systems and user applications is well known in the art. Threads allow multiple execution paths within a single address space (the process context) to run concurrently on a processor. This xe2x80x9cmultithreadingxe2x80x9d increases throughput and modularity in multiprocessor and uniprocessor systems alike. For example, if a thread must wait for the occurrence of an external event, then it stops and the computer processor executes another thread of the same or different computer program to optimize processor utilization. Multithreaded programs also can exploit the existence of multiple processors by running the application program in parallel. Parallel execution reduces response time and improves throughput in multiprocessor (MP) systems.
FIG. 1 illustrates multithreading in a uniprocessor computer system 100, which includes a bus 118 that connects one processor 112 to various I/O devices 114 and a memory device 116. Memory device 116 contains a set of thread context fields 120, one for each thread associated with a particular process. Each thread consists of a set of register values and an execution stack 124. The register values are loaded into the CPU registers when the thread executes. The values are saved back in memory when the thread is suspended. The code that the thread runs is determined by the contents of a program counter within the register set. The program counter typically points to an instruction within the code segment of the application program. Memory device 116 further contains all of the logical addresses for data and instructions utilized by the process, including the stacks of the various threads. After a thread is created and prior to termination, the thread will most likely utilize system resources to gain access to process context 122. Through the process context 122, process threads can share data and communicate with one another in a simple and straightforward manner.
AIX machines support the traditional UNIX operating system (OS) which contains a number of OS commands. The AIX operating system is IBM""s implementation of the UNIX operating system. UNIX is a trademark of UNIX Systems Laboratories, Inc. The NICE command and related operating system""s features purport to allow an administrator the ability to favor or disfavor specific processes as they execute. The result of the NICE command sets an internal NICE value which is utilized in later priority calculations. However, the traditional NICE command""s effectiveness in favoring processes is both weak and tends to diminish over time.
During standard UNIX priority calculation, as each thread runs, it accumulates ticks of central processing unit (CPU) time. The CPU time is divided in half in the priority calculation to allow more CPU time to the thread before its priority degrades. UNIX NICE adjusts the priority by adding a constant, the NICE value, to the priority calculation, where a larger value correlates to a lower priority for the thread.
Thread scheduling is an important aspect of implementing threads. Scheduling is based on a priority calculation where the NICE value adjusts the priority. The system is able to recognize that the thread gets less CPU time and itself attempts to adjust to provide more CPU time; hence there is an internal conflict of sorts which is present in the present art.
The scheduler""s job is to share resources fairly among the runnable threads on a processor based on resource utilization. The only resource that the AIX scheduler deals with is CPU time. The mechanism that the scheduler utilizes to share the CPU is the priority calculation. Threads with numerically lower priorities run ahead of those with numerically higher priorities. (On a MP, affinity considerations may override this rule).
UNIX operating system (OS) has an associated system NICE value which is utilized by the kernel to determine when a thread should be scheduled to run. This value can be decreased to facilitate processes executing quickly or increased so that the processes execute slowly and thus do not interfere with other system activities.
The thread scheduler, which is part of the UNIX kernel, keeps the CPU busy by allocating it to the highest priority thread. The NICE value of a process is utilized to modify the scheduling priority of its threads. The principle factor that is taken into account when calculating the scheduling priority for a process is its recent CPU usage.
The standard UNIX priority implementation (which AIX and probably all other vendors utilize) determines a thread""s dispatching priority as a simple function of its recent CPU utilization history. The NICE facility adjusts the dispatching priorities of select processes on the system by simply adjusting the priority upwards or downwards by adding a fixed amount (the NICE value). Unfortunately, the feedback mechanisms in the scheduler are simultaneously geared to allocating resources fairly to everyone. This results in the diminished effectiveness of NICE mentioned above, because the scheduler will notice the, say, decreased utilization of a thread NICEd down, and soon end up giving that thread equal treatment with all other threads contending for the processor.
Today""s NICExe2x88x9220 (the maximum adjustment allowed) has only a limited effect. For example, if two compute bound threads compete with one NICE""d to xe2x88x9220, after a short time, the default thread gets about 60% of the CPU time while the NICE""d thread gets 40%. This is a rather weak and unsatisfactory result. Although this figure can be increased with AIX schedtune, it degrades the normal behavior of the scheduler. Further, today""s NICE command provides no discrimination between threads after initial advantage at the start of each second.
Many consumers, typically ones with larger systems, are desirous of a better way to allocate processor resources among the competing threads on their systems. Improvement in this area is critically important to large server business, as those consumers generally experience performance problems with mixed workloads on a single systems (i.e., in large MP systems). Consumers are no longer content to dedicate individual machines to specific subsets of their work, but demand to be able to cost effectively share the single large system.
A new priority calculation within the system scheduler is therefore desired to improve the effectiveness of the NICE command beyond merely adding the NICE value to a function.
It would therefore be desirable and advantageous to provide an improved method and system for allocation of system resources among threads with varying priorities utilizing a priority calculation which is a function of both the CPU time and a NICE value, whereby higher priority threads are provided greater system resources and lower priority thread provided less system resources. It would further be desirable to have such a system and method with a feedback mechanism allowing for greater adjustments in priority to lower priority threads so as to prevent the processing system from eliminating the effects of downward adjustments within a small number of clock cycles.
It is therefore one object of the present invention to provide an improved data processing system.
It is another object of the present invention to provide an improved method and system for scheduling threads on a data processing system.
It is yet another object of the present invention to provide a method and system for more scheduling threads on a data processing system wherein system resources are allocated based on a priority determination of a thread.
The foregoing objects are achieved as is now described. A method and system for controlling the allocation of a data processing system""s resources among two or more threads is disclosed. First, a utilization history is created by mapping a thread""s utilization of the system resources. Then, the priority of the thread is calculated utilizing the utilization history and a modified system value. This priority is utilized to determine the allocation of system resources to said thread.
In the preferred embodiment of the invention, the modified system value represents an internal NICE value which has been adjusted. A software algorithm is utilized to calculate the priority of the thread based on the utilization history of a thread by integrating the NICE value in its modified form (or modified system value) in the priority calculation.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.